public class MinimumWindowSubstring {
    // 规则: 窗口内字符内容需要包含 t 中的字符
    // 没有上一题要求这么严格, 窗口大小不固定, 只需要包含有 t 中所有字符即可
    public String minWindow(String _s, String _t) {
        int[] hash1 = new int[123];
        int[] hash2 = new int[123];

        char[] s = _s.toCharArray();
        char[] t = _t.toCharArray();

        for(char c : t) {
            hash2[c]++;
        }

        int n1 = _s.length(), n2 = _t.length();
        int left = 0, right = 0;
        int valid = 0; //记录有效字符个数
        int len = 10_0001; // 假设两个字符串相同且最长
        int begin = 0, end = 10_0001;
        while(right < n1) {
            // 进窗口
            char in = s[right];
            hash1[in]++;
            if(hash1[in] <= hash2[in]) {
                valid++;
            }

            // 2.判断是否要出窗口
            while(valid == n2) {
                if(right - left + 1 < len) {
                    // 更新结果
                    len = right - left + 1;
                    begin = left;
                    end = right;
                }

                // 3.出窗口
                char out = s[left];
                hash1[out]--;
                left++;
                if(hash1[out] < hash2[out]) {
                    valid--;
                }
            }
            right++;
        }
        if(len == 10_0001) {
            return "";
        }

        return _s.substring(begin, end + 1);
    }
}
